package leetcode.easy.q53;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("a:{}",new Solution().maxSubArray(new int[]{ -2,1,-3,4,-1,2,1,-5,4}));
    }
}

/**
 * 分治算法
 */
class Solution2{
    public int maxSubArray(int[] nums) {
"".lastIndexOf(" ");

        return 0;
    }
}
/**
 * 动态规划
 */
class Solution {
    public int maxSubArray(int[] nums) {
        //dp[i]表示以第i个元素结尾的最大和
        /**
         dp[i]=dp[i-1]+nums[i]
         即：以第i个元素结尾的最大和，相当于以i-1结尾的最大和加上i
         思考：当dp[i-1]为负数时，nums[i]加上dp[i-1]一定小于nums[i]本身
         */
        int[] dp =new int[nums.length];
        int sum=nums[0],length=nums.length,max=sum;
        dp[0]=sum;

        for(int i=1;i<length;i++){
            if(dp[i-1]<0){
                dp[i]=nums[i];
            }else{
                dp[i]=dp[i-1]+nums[i];
            }
            if(max<dp[i]){
                max=dp[i];
            }
        }
        return max;

    }
}